package SubjectTree.Five;

import Utility.TreeNode;

public class TrimBST {

/**
 * 难度：中等
 * 
 * 669. 修剪二叉搜索树
 * 	给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索
 * 	树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如
 * 	果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
 * 	所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
 * 	
 * 示例 1：
 * 	输入：root = [1,0,2], low = 1, high = 2
 * 	输出：[1,null,2]
 * 	
 * 示例 2：
 * 	输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
 * 	输出：[3,2,null,1]
 * 	
 * 示例 3：
 * 	输入：root = [1], low = 1, high = 2
 * 	输出：[1]
 * 	
 * 示例 4：
 * 	输入：root = [1,null,2], low = 1, high = 3
 * 	输出：[1,null,2]
 * 	
 * 示例 5：
 * 	输入：root = [1,null,2], low = 2, high = 4
 * 	输出：[2]
 * 	
 * 提示：
 * 	树中节点数在范围 [1, 104] 内
 * 	0 <= Node.val <= 104
 * 	树中每个节点的值都是唯一的
 * 	题目数据保证输入是一棵有效的二叉搜索树
 * 	0 <= low <= high <= 104
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TrimBST tbst = new TrimBST();
		System.out.println(tbst.trimBST(
				TreeNode.MkTree("[3,0,4,null,2,null,null,null,null,1,null,null,null,null,null]"), 1, 3));
	}
	//方法：递归
	public TreeNode trimBST(TreeNode root, int low, int high) {
		if(root==null)return null;
		//node.val < low，那么修剪后的二叉树出现在节点的右边。
		if(root.val<low) return trimBST(root.right, low, high);
		//node.val > high，那么修剪后的二叉树必定出现在节点的左边。
		if(root.val>high) return trimBST(root.left, low, high);
		root.left = trimBST(root.left, low, high);
		root.right = trimBST(root.right, low, high);
		return root;
    }
	//方法：迭代
	public TreeNode trimBST1(TreeNode root, int L, int R) {
        if (root==null) return null;

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root.val < L || root.val > R) {
            if (root.val < L) root = root.right; // 小于L往右走
            else root = root.left; // 大于R往左走
        }
        TreeNode cur = root;
        // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
        while (cur != null) {
            while (cur.left!=null && cur.left.val < L) {
                cur.left = cur.left.right;
            }
            cur = cur.left;
        }
        cur = root;

        // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
        while (cur != null) {
            while (cur.right!=null && cur.right.val > R) {
                cur.right = cur.right.left;
            }
            cur = cur.right;
        }
        return root;
    }
}
